package com.cg.leetcode;

import org.junit.Test;

/**
 * 53. 最大子数组和
 *
 * @program: LeetCode->LeetCode_53
 * @description: 53. 最大子数组和
 * @author: cg
 * @create: 2021-08-21 22:02
 **/
public class LeetCode_53 {

    @Test
    public void test53() {
        System.out.println(maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
        System.out.println(maxSubArray(new int[]{-2, 1}));
    }

    /**
     * 给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     * <p>
     * 示例 1：
     * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
     * 输出：6
     * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
     * <p>
     * 示例 2：
     * 输入：nums = [1]
     * 输出：1
     * <p>
     * 示例 3：
     * 输入：nums = [0]
     * 输出：0
     * <p>
     * 示例 4：
     * 输入：nums = [-1]
     * 输出：-1
     * <p>
     * 示例 5：
     * 输入：nums = [-100000]
     * 输出：-100000
     *
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        // 动态规划解法
        int max = nums[0];
        for (int i = 0; i < nums.length; i++) {
            int temp = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                temp += nums[j];
                max = Math.max(max, temp);
            }
            max = Math.max(max, nums[i]);
        }
        /*
        // 优化
        int per = 0, max = nums[0];
        for (int num : nums) {
            per = Math.max(per + num, num);
            max = Math.max(per, max);
        }
        */
        /*// 贪心解法
        int sum = 0, max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            max = Math.max(max, count);
            if (sum <= 0) {
                sum = 0;
            }
        }*/
        return max;
    }

}
